package com.dylon.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] a = new int[]{2,5,3,1,4,13,11,26,24};
        System.out.println(Arrays.toString(a));
        mergesort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));
    }


    private static void mergesort(int[] array, int left, int right) {
        int mid = (left+right)/2;
        if (left<right) {
            mergesort(array, left, mid);
            mergesort(array, mid+1, right);
            merge(array, left, mid, right);
        }
    }

    private static void merge(int[] array, int l, int mid, int r) {
        int lindex = l, rindex = mid+1;
        int[] team = new int[r-l+1];
        int teamindex = 0;
        while (lindex <= mid && rindex <= r) {// 先左右比较合并
            if (array[lindex] <= array[rindex]) {
                team[teamindex++] = array[lindex++];
            } else {
                team[teamindex++] = array[rindex++];
            }
        }
        while (lindex<=mid) { // 当一个越界后剩余按序列添加即可
            team[teamindex++] = array[lindex++];
        }
        while (rindex<=r) {
            team[teamindex++] = array[rindex++];
        }
        for (int i=0; i<teamindex; i++)  {
            array[l+i] = team[i];
        }
    }

    /*
    在归并类排序一般只讲归并排序，但是归并排序也分二路归并、多路归并，这里就讲较多的二路归并排序，且用递归方式实现
    归并和快排都是「基于分治算法」的，分治算法其实应用挺多的，很多分治会用到递归，但事实上「分治和递归是两回事」。
        分治就是分而治之，可以采用递归实现，也可以自己遍历实现非递归方式。
        而归并排序就是先将问题分解成代价较小的子问题，子问题再采取代价较小的合并方式完成一个排序。

    归并的思想是这样的：
        现将整串先进行递归拆分（折半拆分）成单个
        再将序列两两归并成有序序列
        就这样一直到最后这个串串只剩一个
        这个耗费的总次数logn。每次操作的时间复杂的又是O(n)。所以总共的时间复杂度为O(nlogn).

           2,5,3,1,4,13,11,26,24
         2,5,3,1,4     13,11,26,24
       2,5,3   1,4     13,11      26,24
     2,5   3  1   4   13   11    26   24
    2  5   3  1   4   13   11    26   24
     2,5   3  1   4   11,13      26   24
      2,3,5   1,4     11,13   24,26
       1,2,3,4,5   11,13,24,26
        1,2,3,4,5,11,13,24,26


     */

}
